package com.yaoli.ajob;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by will on 2017/5/6.
 */
public class _279_PerfectSquares {
    public static void main(String[] args) {
        _279_PerfectSquares perfectSquares = new _279_PerfectSquares();

        System.out.println(perfectSquares.numSquares2(12));
    }

    /**
     * 宽度 遍历
     *
     * @param n
     * @return
     */
    public int numSquares2(int n) {


        Queue<Integer> queue = new LinkedList<Integer>();

        queue.add(n);

        int level = 0;

        boolean flag = false;

        while(!queue.isEmpty()){
            int len = queue.size();

            level++;

            while(len != 0){
                int temp = queue.poll();

                int m = (int)Math.sqrt(temp);

                for(int i = m; i >= 1; i --){
                    int leftNum = temp - i*i;
                    if(leftNum == 0){
                        flag = true;
                        break;
                    }
                    queue.add(leftNum);
                }

                if(flag == true){
                    break;
                }

                len --;
            }

            if(flag == true){
                break;
            }
        }


        return level;
    }
    public int numSquares(int n) {

        ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
        queue.add(n);

        //深度
        int depth = 1, m = 1, tmp = 0;

        while(true){

            //
            if(m == 0){
                depth++;
                m = tmp;
                tmp = 0;
            }

            //
            int cur = queue.remove();
            m--;

            int l = (int) Math.sqrt(cur);
            for(int i=l; i>0; i--){
                int sq = i*i;
                int delta = cur - sq;
                if(delta == 0)
                    return depth;
                queue.add(delta);
                tmp++;
            }
        }
    }
}
